package com.lga.dataStructure;

import jdk.nashorn.internal.ir.BinaryNode;
import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 自定义二叉树
 */
public class BinaryTree {

    private TreeNode root;
    private int[] nodeList;

    public BinaryTree(TreeNode root, int[] nodeList) {
        this.root = root;
        this.nodeList = nodeList;
        initBinaryTree(this.root, nodeList);
    }

    /**
     * 广度优先搜索(BFS)：
     * 按层次去遍历，从上到下，从左右到右
     */
    public void breadFisrtSearch() {
        Queue queue = new LinkedList();
        if (root != null) {
            queue.add(root);
        }

        while (!queue.isEmpty()) {

            TreeNode  rootTemp = (TreeNode) queue.poll();
            System.out.print(rootTemp.value + " ");

            if (rootTemp.getLeftNode() != null) {
                queue.offer(rootTemp.getLeftNode());
            }

            if (rootTemp.getRightNode() != null) {
                queue.offer(rootTemp.getRightNode());
            }

        }
    }

    /**
     * 深度优先遍历(DFS)
     */
    public void depthFirstSearch() {
        Stack stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode TreeNode = (TreeNode) stack.pop();
            System.out.print(TreeNode.getValue() + " ");
            if (TreeNode.getRightNode() != null) {
                stack.push(TreeNode.getRightNode());
            }
            if (TreeNode.getLeftNode() != null) {
                stack.push(TreeNode.getLeftNode());
            }
        }

    }

    /**
     * 前序遍历
     * @param root
     */
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.getValue() +" ");
        preOrder(root.getLeftNode());
        preOrder(root.getRightNode());

    }

    /**
     * 中序遍历
     * @param root
     */
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.getLeftNode());
        System.out.print(root.getValue() +" ");
        inOrder(root.getRightNode());

    }

    /**
     * 后序遍历
     * @param root
     */
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.getLeftNode());
        postOrder(root.getRightNode());
        System.out.print(root.getValue() +" ");
    }

    private void initBinaryTree(TreeNode root, int[] nodeList) {

        if (nodeList == null) {
            return;
        }
        for (int node : nodeList) {
            insertNode(root, new TreeNode(node));
        }

    }

    private void insertNode(TreeNode root, TreeNode childNode) {
        if (root.getValue() > childNode.getValue()) {//插入到左边
            if (root.leftNode == null) {
                root.leftNode = childNode;
                return;
            }
            insertNode(root.leftNode, childNode);

        } else {//插入右边
            if (root.rightNode == null) {
                root.rightNode = childNode;
                return;
            }
            insertNode(root.rightNode, childNode);

        }
    }

    public static class TreeNode {

        private int value;
        private TreeNode leftNode;
        private TreeNode rightNode;

        public TreeNode(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public TreeNode getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(TreeNode leftNode) {
            this.leftNode = leftNode;
        }

        public TreeNode getRightNode() {
            return rightNode;
        }

        public void setRightNode(TreeNode rightNode) {
            this.rightNode = rightNode;
        }
    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree(new TreeNode(8), new int[]{3, 5, 20, 15, 2, 29, 1, 4, 6, 13, 16, 21, 30});
        binaryTree.breadFisrtSearch();
        System.out.println("--------------");
        binaryTree.depthFirstSearch();
        System.out.println("--------");
        System.out.println("前序遍历：");
        binaryTree.preOrder(binaryTree.root);
        System.out.println();
        System.out.println("中序遍历：");
        binaryTree.inOrder(binaryTree.root);
        System.out.println();
        System.out.println("后序遍历：");
        binaryTree.postOrder(binaryTree.root);
    }
}
